/*
 * gcc -std=c++0x stdset.cpp -o stdset
 */
#include <iostream>
#include <string>
#include <set>
#include <unordered_set>
using namespace std;

typedef struct _value_t {
    int v;
    string sv;
    _value_t() : v(0), sv() { } /* required for sets */
    _value_t(int v, const char *sv) {
        this->v = v;
        this->sv = sv;
    }
} value_t;

bool operator<(const value_t &a, const value_t &b) /* for ordered versions */
{
    return (a.v < b.v) || (a.v == b.v && a.sv < b.sv);
}

bool operator==(const value_t &a, const value_t &b) /* for unordered versions */
{
    return (a.v == b.v && a.sv == b.sv);
}

typedef struct _hash_value_t { /* for unordered versions */
    size_t operator()(const value_t &t) const {
        size_t v1 = hash<int>()(t.v);
        size_t v2 = hash<string>()(t.sv);
        return v1 ^ v2;
    }
} hash_value_t;

void test_set()
{
    cout << "--- test std::set ---" << endl;
    set<value_t> s;
    s.insert(value_t(111, "111s"));
    s.insert(value_t(222, "222s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(222, "444s"));
    for (set<value_t>::const_iterator it = s.begin(); it != s.end(); ++it) {
        cout << "value=[" << it->v << "," << it->sv << "]." << endl;
    }
}

void test_multiset()
{
    cout << "--- test std::multiset ---" << endl;
    multiset<value_t> s;
    s.insert(value_t(111, "111s"));
    s.insert(value_t(222, "222s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(222, "444s"));
    for (multiset<value_t>::const_iterator it = s.begin(); it != s.end(); ++it) {
        multiset<value_t>::const_iterator it2 = s.upper_bound(*it);
        for ( ; it != it2; ++it) {
            cout << "value=[" << it->v << "," << it->sv << "]" << endl;
        }
        --it;
    }
}

/* hash */
void test_unordered_set()
{
    cout << "--- test std::unordered_set ---" << endl;
    unordered_set<value_t, hash_value_t> s;
    s.insert(value_t(111, "111s"));
    s.insert(value_t(222, "222s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(222, "444s"));
    int count = s.bucket_count();
    for (int i = 0; i < count; ++i) {
        cout << "bucket=#" << i << ":" << endl;
        for (auto it = s.cbegin(i); it != s.cend(i); ++it) {
            cout << "    value=[" << it->v << "," << it->sv << "]." << endl;
        }
    }
}

/* hash */
void test_unordered_multiset()
{
    cout << "--- test std::unordered_multiset ---" << endl;
    unordered_multiset<value_t, hash_value_t> s;
    s.insert(value_t(111, "111s"));
    s.insert(value_t(222, "222s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(333, "333s"));
    s.insert(value_t(222, "444s"));
    int count = s.bucket_count();
    for (int i = 0; i < count; ++i) {
        cout << "bucket=#" << i << ":" << endl;
        for (auto it = s.cbegin(i); it != s.cend(i); ++it) {
            cout << "    value=[" << it->v << "," << it->sv << "]." << endl;
        }
    }
}

int main()
{
    /*
     * - http://www.cplusplus.com/reference/set/set/
     * - Sets are containers that store unique elements following a specific
     * order.
     * - Sets are typically implemented as binary search trees.
     */
    test_set();
    /*
     * - http://www.cplusplus.com/reference/set/multiset/
     * - Multisets are containers that store elements following a specific
     * order, and where multiple elements can have equivalent values.
     * - Multisets are typically implemented as binary search trees.
     */
    test_multiset();
    /*
     * - http://www.cplusplus.com/reference/unordered_set/unordered_set/
     * - Unordered sets are containers that store unique elements in no
     * particular order, and which allow for fast retrieval of individual
     * elements based on their value.
     * - Internally, the elements in the unordered_set are not sorted in any
     * particular order, but organized into buckets depending on their hash
     * values to allow for fast access to individual elements directly by their
     * values (with a constant average time complexity on average).
     */
    test_unordered_set();
    /*
     * - http://www.cplusplus.com/reference/unordered_set/unordered_multiset/
     * - Unordered multisets are containers that store elements in no
     * particular order, allowing fast retrieval of individual elements based
     * on their value, much like unordered_set containers, but allowing
     * different elements to have equivalent values.
     * - Internally, the elements in the unordered_multiset are not sorted in
     * any particular, but organized into buckets depending on their hash
     * values to allow for fast access to individual elements directly by their
     * values (with a constant average time complexity on average).
     */
    test_unordered_multiset();

    return 0;
}
